package com.lijing.ShellSort;
//
public class Shell {
    public static void sort(Comparable[] arr){
        int step = 1;
        while(step<arr.length/2){
            step = 2*step+1;
        }
        for (int gap = step; gap > 0; gap /= 2) {//分组，步长为gap
            //对每一组进行插入排序
            for (int i = gap; i < arr.length; i++) {
                for (int j = i; j > gap; j -= gap) {
                    if (greater(arr[j-gap],arr[j])){
                        exch(arr,j-gap,j);
                    }else {
                        break;
                    }
                }
            }
        }
    }

    /**
     * compare two item
     * @param v item1
     * @param w item2
     * @return return true if v>w
     */
    private static boolean greater(Comparable v, Comparable w){
        return v.compareTo(w)>0;
    }

    //exchange two items
    private static void exch(Comparable[] a, int i, int j){
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
